package class37;

import java.lang.annotation.Target;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class BestTimetoBuyandSellStockFollow {

    public static int maxProfit1(int K, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int N = prices.length;
        if (K >= N / 2) {
            return allTrans(prices);
        }
        int[][] dp = new int[N][K + 1];
        int ans = 0;
        //一列一列遍历
        for (int j = 1; j <= K; j++) {
            //dp[i][j] = dp[0][j]                    ---1)
            //           dp[1][j-1]  - [1]  +  [1]   ---2)1>
            //                      t       +  [1]
            //           dp[0][j-1]  - [0]  +  [1]   ---2)1>
            //                      t       +  [1]
            //从第一列开始遍历，所以我么那必须先设置好t的值
            int t = dp[0][j - 1] - prices[0];
            for (int i = 1; i < N; i++) {
                int nextT = Math.max(t, dp[i][j - 1] - prices[i]);
                //情况一和情况二取最大值
                dp[i][j] = Math.max(dp[i - 1][j], t + prices[i]);
                //设置下一轮的t值
                t = nextT;
                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans;
    }

    public static int maxProfit2(int K, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int N = prices.length;
        if (K >= N / 2) {
            return allTrans(prices);
        }
        //dp一维表，做了空间压缩
        int[] dp = new int[N];
        int ans = 0;
        for (int tran = 1; tran <= K; tran++) {
            int pre = dp[0];
            int best = pre - prices[0];
            for (int index = 1; index < N; index++) {
                pre = dp[index];
                dp[index] = Math.max(dp[index - 1], prices[index] + best);
                best = Math.max(best, pre - prices[index]);
                ans = Math.max(dp[index], ans);
            }
        }
        return ans;
    }

    public static int allTrans(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            ans += Math.max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[maxSize];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxSize = 20;
        int maxValue = 20;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int K = 8;
            int res1 = maxProfit1(K, arr);
            int res2 = maxProfit2(K, arr);
            if (res1 != res2) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(res1);
                System.out.println(res2);
                break;
            }
        }
        System.out.println("test end!");
    }
}
